package com.sufen.seckill.study.LeetCode;

import com.sufen.seckill.study.LeetCodeHelper.TreeNode;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * @Author sufen
 * @Date 2021/11/4 15:35
 * @Version 1.0
 * 功能描述：
 */
public class Offer_07_重建二叉树 {

    public static void main(String[] args) {
        int[] preorder={3,9,20,15,7};
        int[] inorder={9,3,15,20,7};
        TreeNode res=buildTree(preorder,inorder);
        //输出
        List<Integer> list=new ArrayList<>();
        Queue<TreeNode> queue=new LinkedList<>();
        queue.add(res);
        while(!queue.isEmpty()){
            int size=queue.size();
            for(int i=0;i<size;i++){
                TreeNode root=queue.poll();
                if(root==null){
                    continue;
                }
                list.add(root.val);
                queue.add(root.left);
                queue.add(root.right);
            }
        }
        System.out.println(list);
    }

    public static TreeNode buildTree(int[] preorder, int[] inorder) {
        return build_tree(preorder,0,preorder.length,inorder,0,inorder.length);
    }

    public static TreeNode build_tree(int[] preorder,int pre_start,int pre_end,int[] inorder,int in_start,int in_end){
        if(pre_start>=pre_end){
            return null;
        }

        //找根。
        int gen=preorder[pre_start];
        int in_index=0;
        for(int i=in_start;i<in_end;i++){
            if(inorder[i]==gen){
                in_index=i;
            }
        }
        int length=in_index-in_start;
        //到此，根的index为in_index,左子树的大小为length;

        //递归：
        TreeNode root=new TreeNode(gen);
        root.left=build_tree(preorder,pre_start+1,pre_start+1+length,inorder,in_start,in_index);
        root.right=build_tree(preorder,pre_start+1+length,pre_end,inorder,in_index+1,in_end);

        return root;

    }
}
